package coding_interviews;

import java.util.Arrays;

/**
 * @Author 孔德成
 * @Slogan 致敬大师，致敬未来的你
 * @desc 数组中重复的数字
 * @link https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
 */
public class Offer03 {
    /**
     * 数组代替哈希表解法
     *
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {
        // 1. 初始化一个数组
        int[] bucket = new int[nums.length];
        Arrays.fill(bucket, -1);
        for (int i = 0; i < nums.length; i++) {
            // 2. 判断当前元素是否已经存在
            if (bucket[nums[i]] != -1) {
                // 如果存在，则直接返回
                return nums[i];
            }
            // 否则的话，将当前元素作为索引，当前元素的下标作为值，填入数组中，
            // 方便后续的查找判重
            bucket[nums[i]] = i;
        }
        return -1;
    }

    /**
     * 核心思路：记录每个元素的出现次数
     *
     * @param nums
     * @return
     */
    public int s1(int[] nums) {
        // 记录 nus 中每个元素的出现次数
        // index=元素, value=次数
        int[] ints = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (ints[nums[i]] != 0) {
                // 0表示元素出现次数为0
                return nums[i];
            } else {
                // 出现次数+1
                ints[nums[i]]++;
            }

        }
        return -1;

    }

}
